<?php

class Point
{
	public function __construct($x, $y)
	{
		$this->x = $x;
		$this->y = $y;
	}

	public $x;
	public $y;
}

class Size
{
	public function __construct($width, $height)
	{
		$this->width = $width;
		$this->height = $height;
	}

	public $width;
	public $height;
}

class Bounds
{
	public function __construct($location, $size)
	{
		$this->location = $location;
		$this->size = $size;
	}

	public $location;
	public $size;
	
	public function getSurface()
	{
	    return $this->size->width * $this->size->height;
	}
}

// Input entry to place in the grid.
class GridEntry
{
	public function __construct($weight)
	{
		$this->weight = $weight;
	}

	// The weight is a number between 0 and 1.
	public $weight;
	// Title of the article, if any.
	public $title;
}

// Output item of the grid.
class GridNewnit
{
	// Location of the newnit.
	public $bounds;
	// Source grid entry.
	public $gridEntry;
}

// Used to layout grid entries into the grid.
class GridLayouter
{
	private $newnits;
	private $grid;
	private $entries;
	private $wildZones;
	private $totalWeight;
	private $totalSize;

	private static function entryCompare($e1, $e2)
	{
		return $e1->weight > $e2->weight;
	}
	
	private static function wildZoneCompare($w1, $w2)
	{
	    return $w1->getSurface() >  $w2->getSurface();
	}
	
	/// Try to place the remaining entries in the grid.
	public function tryPlace()
	{
		// Stopping condition: all entries has been placed successfully.
		if (count($this->entries) == 0)
			return 0;
			
		// Stopping condition: there is no wild zone to place the entry.
		if (count($this->wildZones) == 0)
			return -1;
		
		// We grab the largest entry.
		$localEntry = array_pop($this->entries);
		$wildZone = array_pop($this->wildZones);
		//$bounds = clone $wildZone;
	
		// We guess the target size.
		$localSize = new Size(ceil(pow(($localEntry->weight / $this->totalWeight), 1/2) * $this->totalSize->width),
		    ceil(pow(($localEntry->weight / $this->totalWeight), 1/2) * $this->totalSize->height));
		
	    // We clamp if we're outer the wild zone.
	    if ($localSize->width > $wildZone->size->width)
	        $localSize->width = $wildZone->size->width;
		if ($localSize->height > $wildZone->size->height)
	        $localSize->height = $wildZone->size->height;    

        
        $nwzCount = 0;
        $lastResult = 0;
        
		// Main loop: we try to place the entry and the subentries
		// until it all fits nicely
		do
		{
		    // Clean wildzones that do not worked.
		    while ($nwzCount > 0)
		    {
		        array_pop($this->wildZones);
		        $nwzCount--;
		    }
		    
		    if ($lastResult != 0)
		    {
		        if ($lastResult < 0)
		        {
	                if ($localSize->width > $localSize->height)
    	                $localSize->width--;
                    else
                        $localSize->height--;
		        }
		        else
		        {
		            if ($localSize->width < $localSize->height)
    	                $localSize->width++;
                    else
                        $localSize->height++;
		        }
                if ($localSize->width == 0 || $localSize->height == 0)
                {
    			    // Just restore the entry and wild zones
    			    array_push($this->entries, $localEntry);
    			    array_push($this->wildZones, $wildZone);
    				return -1;
                }
		    }
		    
            // We create new wild zones in the gaps.
            $nwzCount = 0;
            $newWildZones = array();
            
            // Check whether it's better to split horizontally or vertically
            $splitDirection = ($wildZone->size->width) * ($wildZone->size->height - $localSize->height) >
                ($wildZone->size->width - $localSize->width) * ($wildZone->size->height);
            
            if ($localSize->height < $wildZone->size->height)
            {
                // Horizontal wild zone.
                $newWildZone = new Bounds(new Point($wildZone->location->x,
    				$wildZone->location->y  + $localSize->height),
    				new Size($splitDirection ? $wildZone->size->width : $localSize->width,
    				$wildZone->size->height - $localSize->height));
    			
    			array_push($newWildZones, $newWildZone);
    			$nwzCount++;
            }
            if ($localSize->width < $wildZone->size->width)
            {
                // Vertical wild zone (does not go to the bottom of the wildzone).
                $newWildZone = new Bounds(new Point($wildZone->location->x + $localSize->width,
    				$wildZone->location->y),
    				new Size($wildZone->size->width - $localSize->width,
    				$splitDirection ? $localSize->height : $wildZone->size->height));
    			
    			array_push($newWildZones, $newWildZone);
    			$nwzCount++;
            }
            
            usort($newWildZones, 'GridLayouter::wildZoneCompare');
            
            foreach ($newWildZones as $newWildZone)
            {
                array_push($this->wildZones, $newWildZone);
            }
            
			$nwzCount--;
			
			$lastResult = $this->tryPlace();
		} while ($lastResult != 0);
		
		$localNewnit = new GridNewnit();
		$localNewnit->bounds = new Bounds($wildZone->location, $localSize);
		$localNewnit->entry = $localEntry;
	    
		array_push($this->newnits, $localNewnit);
	    
		return 0;
	}
	
	
	public function layout($entries, $gridSize)
	{
		$this->newnits = array ();
		$this->grid = array ();
		
		$this->entries = $entries;
		usort($this->entries, 'GridLayouter::entryCompare');
		
		foreach ($this->entries as $entry)
		{
		    $this->totalWeight += $entry->weight;
		}
		$this->totalSize = $gridSize;
		
		// We start with the first entry and we want to fill the whole grid
		$this->wildZones = array(new Bounds(new Point(0, 0), clone $gridSize));
		$this->tryPlace();
		
		return $this->newnits;
	}

}
